Statement#

Suppose you are given a string, s. You need to perform the minimum number of cuts to divide the string into substrings, such that all the resulting substrings are palindromes.

Let’s say you have the following string:

  • “apple”

The resulting substrings after performing the minimum number of cuts are:

  • “a”|“pp”|“l”|“e”

So, a minimum of 33 cuts are required.

Constraints:

  • 11 \leq s.length 600\leq 600
  • s consists of only lowercase English characters.

Examples#

No.

s

cuts

1

"sleek"

3

2

"adjacent"

7

3

"radar"

0

Try it yourself#

Implement your solution in the following coding playground.

Python
usercode > main.py
Input #1
Palindrome Partitioning

Note: If you clicked the “Submit” button and the code timed out, this means that your solution needs to be optimized in terms of running time.

Hint: Use dynamic programming and see the magic.

Solution#

We will first explore the naive recursive solution to this problem and then see how it can be improved using the Palindromic Subsequence dynamic programming pattern.

Naive approach#

A naive approach would be to generate combinations of all possible cuts that can be placed on the string such that all the resulting substrings are palindromes. We will then select the minimum number of cuts.

For example, we have the following string:

s: “abac”

To find the minimum number of cuts, we try all possible combinations:

  • “a” |“b” |“a” |“c” — 33 cuts
  • “aba” | “c” — 11 cut

The calculation above shows that we need a recursive solution to make all possible combinations. In other words, we divide the problem into subproblems by placing cuts at every possible position in the string. The position to place a cut is determined using a variable, k, that ranges from, i to j - 1, where i and j are the start and end indexes of the current substring respectively. We store the minimum number of cuts in a variable, result, which is initially set to j, i.e., the maximum number of cuts that can be placed on a string to make the resulting substrings (consisting of one character each) palindromes. This is done based on the following rules:

  • Base case: If we have reached the end of the substring, or the current substring is a palindrome, we return 00.

  • Otherwise, we run a loop from k = 0 to k = s.length - 1. On each iteration, we place a cut after the kthk^{th} index of the string and divide it into two halves. Since we’ve placed one cut, the resulting cost of placing more cuts follows the following recurrence relation, where we now re-evaluate these resulting two halves:

    totalCuts = 1 + min_cuts(s, i, k) + min_cuts(s, k + 1, j)

    After an iteration for a value of k is complete, i.e., we have found the total number of cuts that can be placed for a value of k, we take the minimum of the current value of result and totalCuts and store this in result.

  • We repeat the above process for all values of k. When the loop ends, result stores the minimum number of cuts, and we return result.

Let’s implement the algorithm as discussed above:

Palindromic Partitioning using recursion

Note: Please observe that if you include the test case commented out in the driver code, the solution is likely to time out. Try to solve the larger problem using the dynamic programming solutions provided below and see the difference.

Time complexity#

The time complexity of the naive approach is O(2n)O(2^n), where nn is the total number of characters in the string.

Space complexity#

As the maximum depth of the recursive call tree is nn, and each call stores its data on the stack, the space complexity of this approach is O(n)O(n).

Optimized solution using dynamic programming#

Now, let’s improve the recursive solution using top-down and bottom-up approaches.

Top-down solution#

The top-down solution, commonly known as the memoization technique, is an enhancement of the recursive solution. It overcomes the problem of calculating redundant solutions over and over again by storing them in a table. In the recursive approach, the following two variables kept changing:

  • The start index of the substring, i.
  • The end index of the substring, j.

We will use a 2-D table, dp, with i rows and j columns to store the result, i.e., the total number of cuts for the substring, s[i]…s[j].

In addition, we will use a second 2-D table, palindrome_table, with i rows and j columns to store whether the current substring, s[i]…s[j], is a palindrome or not.

At any later time, if we encounter the same sub-problem, we can return the stored result from the table with an O(1)O(1) look-up instead of re-calculating that subproblem.

Let’s implement the algorithm as discussed above:

Palindromic Partitioning using memoization

Note: Please observe that if you now uncomment the large test case in the driver code, the dynamic programming solution will still work.

Time complexity#

As we avoided redundant calculations by storing all the intermediate results in two 2-D tables, the time complexity of this approach is reduced to O(n3)O(n^3), where nn is the number of characters in the string.

Space complexity#

We now need O(n2)O(n^2) space in memory to store intermediate values.

Bottom-up solution#

The bottom-up solution, also known as the tabulation technique, is an iterative method of solving dynamic programming problems.

We will create a 1-D array, dp, of size nn. This array will have the following properties:

  • Each entry, dp[i], stores the minimum number of cuts required in the substring, s[i]…s[n].

  • The array will initially store the value of inf for all of its entries.

We will also create a 2-D table, palindrome_table, of size (n×n)(n \times n), which stores whether each substring is a palindrome or not. The table will be filled with 11s and 00s in the following way:

  • If the substring, s[i]…s[j], is a palindrome, palindrome_table[i][j] will be 11.

  • Otherwise, if s[i]…s[j], is not a palindrome, palindrome_table[i][j] will be 00.

We will traverse the indexes, i, of s from right to left and fill the dp array in the following manner:

  • If palindrome_table[i][n - 1] is 11, this means s[i]…s[n - 1] is a palindrome, so we fill dp[i] with 00 since no cuts are required.

    if palindrome_table[i][- 1] == 1:
       dp[i] = 0
  • Otherwise, we will look for a palindrome in the remaining substring s[i]…s[n - 2]. We traverse the indexes, j, of this substring from right to left in the following manner:

    • We check whether palindrome_table[i][j] is 11. If it is, s[j]…s[n - 1] is a palindrome. So we update dp[i] with the minimum of its current value and 1 + dp[j + 1]:

      if palindrome_table[i][j] == 1:
         dp[i] = min(dp[i], 1 + dp[+ 1])

After the outer loop has ended, dp[0] will contain the minimum cuts required on the entire string, so we return dp[0].

Let’s look at the following illustration to get a better understanding of the solution:

Created with Fabric.js 3.6.6 We start by filling palindrome_table to store information about the palindromic properties of each substring.

1 of 21

Created with Fabric.js 3.6.6 All single character substrings with the same values of i and j are substrings of each other. So the diagonals will be all 1s.

2 of 21

Created with Fabric.js 3.6.6 We will now traverse palindrome_table from bottom right to top left while skipping the diagonals since they're already filled and also indexes wherei is greater than j, since those substrings are invalid.

3 of 21

Created with Fabric.js 3.6.6 palindrome_table[2, 3]: This entry remains 0, since s[2]..s[3] is not a palindrome.

4 of 21

Created with Fabric.js 3.6.6 palindrome_table[1, 3]: This entry remains 0, since s[1]..s[3] is not a palindrome.

5 of 21

Created with Fabric.js 3.6.6 palindrome_table[1, 2]: This entry remains 0, since s[1]..s[2] is not a palindrome.

6 of 21

Created with Fabric.js 3.6.6 palindrome_table[0, 3]: This entry remains 0, since s[0]..s[3] is not a palindrome.

7 of 21

Created with Fabric.js 3.6.6 palindrome_table[0, 2]: This entry will be changed to 1, since s[0]..s[2] is a palindrome.

8 of 21

Created with Fabric.js 3.6.6 palindrome_table[0, 1]: This entry remains 0, since s[0]..s[1] is not a palindrome.

9 of 21

Created with Fabric.js 3.6.6 We will now traverse s in reverse order to fill the dparray.

10 of 21

Created with Fabric.js 3.6.6 i = 3Condition: palindrome_table[3][3] == 1, TRUESo dp[3] = 0, since s[3]..s[3] is a palindrome and no cuts are required.

11 of 21

Created with Fabric.js 3.6.6 i = 2Condition: palindrome_table[2][3] == 1, FALSESo we traverse the remaining substring, s[2]..s[2] in reverse order, to check if a palindrome can be found in any of its substrings.

12 of 21

Created with Fabric.js 3.6.6 i = 2Condition: palindrome_table[2][2] == 1, TRUESo we set dp[2] = min(inf, 1 + 0) = 1, since as[2]..s[2] is a palindrome and a cut can be placed.

13 of 21

Created with Fabric.js 3.6.6 i = 1Condition: palindrome_table[1][3] == 1, FALSESo we traverse the remaining substring, s[1]..s[2] in reverse order, to check if a palindrome can be found in any of its substrings.

14 of 21

Created with Fabric.js 3.6.6 i = 1Condition: palindrome_table[1][2] == 1, FALSESo we traverse the remaining substring, s[1]..s[1] in reverse order, to check if a palindrome can be found in any of its substrings.

15 of 21

Created with Fabric.js 3.6.6 i = 1Condition: palindrome_table[1][1] == 1, TRUESo we set dp[1] = min(inf, 1 + 1) = 2, sinces[1]..s[1] is a palindrome and a cut can be placed.

16 of 21

Created with Fabric.js 3.6.6 i = 0Condition: palindrome_table[0][3] == 1, FALSESo we traverse the remaining substring, s[0]..s[2] in reverse order, to check if a palindrome can be found in any of its substrings.

17 of 21

Created with Fabric.js 3.6.6 i = 0Condition: palindrome_table[0][2] == 1, TRUESo we set dp[0] = min(inf, 1 + 0) = 1, sinces[0]..s[2] is a palindrome and a cut can be placed.We will continue to traverse the rest of the substring to check if a lower number of cuts can be placed.

18 of 21

Created with Fabric.js 3.6.6 i = 0Condition: palindrome_table[0][1] == 1, FALSESo we traverse the remaining substring, s[0]..s[0] in reverse order, to check if a palindrome can be found in any of its substrings.

19 of 21

Created with Fabric.js 3.6.6 i = 0Condition: palindrome_table[0][0] == 1, TRUESo we set dp[0] = min(1, 2 + 1) = 1, since eventhough s[0]..s[0] is a palindrome, a fewer numberof cuts can be placed when considering the substring, s[0]..s[2].

20 of 21

Created with Fabric.js 3.6.6 The outer loop has ended. dp[0] now contains 1, sowe need a minimum of 1 cut to divide the string intopalindromic substrings. Hence, we return1.

21 of 21

Let’s implement the algorithm as discussed above:

Palindromic Partitioning using tabulation

Note: Please observe that if you now uncomment the large test case in the driver code, the dynamic programming solution will still work.

Time complexity#

As we created a 2-D table to store the results of subproblems that would be used later on, therefore, the time complexity of this approach will also be O(n2)O(n^2).

Space complexity#

We need O(n2)O(n^2) space in memory to store the intermediate values.

Count of Palindromic Substrings

Where to Go from Here?